Biuro podróży
Limit pamięci: 128 MB
Bajtazar jest nauczycielem w szkole podstawowej w Bajtołach Dolnych.
Korzystając z tego, że pogoda całkiem dopisuje, Bajtazar
chciałby zabrać swoją klasę na wycieczkę autokarową do stolicy kraju,
Bajtogrodu.
Do pomocy w organizacji wycieczki Bajtazar postanowił zatrudnić
biuro podróży BajTour.
Ulice w centrum Bajtogrodu tworzą regularną siatkę: każda ulica biegnie
albo z zachodu na wschód, albo z południa na północ,
a odległości między dwiema sąsiednimi równoległymi ulicami są równe
i wynoszą jeden kilometr.
Przy niektórych skrzyżowaniach znajdują się atrakcje turystyczne.
Bajtoccy przewodnicy każdej atrakcji przypisali pewien współczynnik ciekawości:
im wyższy współczynnik, tym dana atrakcja jest ciekawsza dla zwiedzających.
Bajtazar wie, że jego podopieczni szybko się nudzą, dlatego chciałby, aby
kolejno zwiedzane atrakcje miały coraz większe współczynniki ciekawości.
Biuro BajTour zgodziło się spełnić wymagania Bajtazara, ale
przy tym chciałoby na wycieczce jak najwięcej zarobić.
Biuro pobiera stałą stawkę jednego bajtalara za każdy kilometr trasy autokaru.
Przejeżdżając między dwiema kolejnymi atrakcjami na trasie zwiedzania, autokar
porusza się zawsze najkrótszą trasą biegnącą wzdłuż ulic Bajtogrodu.
Ponadto, BajTour zarabia w jeszcze inny sposób: zarządcy niektórych atrakcji
płacą biuru za przyprowadzanie wycieczek.
Celem BajTouru jest zaproponować trasę zgodną z warunkami postawionymi
przez Bajtazara, która zagwarantuje BajTourowi możliwie największy zysk.
Czy pomógłbyś w wyznaczeniu odpowiedniej trasy?
Uwaga: przejechanie obok atrakcji turystycznej bez wysiadania nie liczy się
jako jej zwiedzenie!
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
(), oznaczające liczbę ulic biegnących z zachodu
na wschód oraz liczbę ulic biegnących z południa na północ.
Dalej następuje wierszy zawierających opis atrakcji turystycznych.
W -tym wierszu znajduje się liczb całkowitych ()
oznaczających współczynniki ciekawości atrakcji turystycznych
rozmieszczonych na skrzyżowaniach -tej ulicy biegnącej ze wschodu na
zachód z kolejnymi ulicami biegnącymi z południa na północ.
Współczynnik oznacza brak atrakcji turystycznej, natomiast dodatnie
współczynniki opisują poszczególne atrakcje.
Wiadomo, że w Bajtogrodzie jest co najmniej jedna atrakcja turystyczna.
Każdy z kolejnych wierszy zawiera po liczb całkowitych ().
Liczba , czyli -ta liczba w -tym z tych wierszy, oznacza kwotę (w bajtalarach), jaką
biuro otrzymuje za wysłanie wycieczki do atrakcji opisanej współczynnikiem ciekawości .
Jeśli przy skrzyżowaniu nie ma atrakcji, odpowiadająca mu liczba jest równa .
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą,
oznaczającą (wyrażony w bajtalarach) zysk z najbardziej dochodowej dla biura trasy, odwiedzającej pewne atrakcje
turystyczne w kolejności ściśle rosnących współczynników ciekawości.
Przykład
Dla danych wejściowych:
4 5
1 2 6 0 2
1 3 4 0 4
0 0 4 0 3
2 2 0 0 4
1 3 5 0 2
2 8 1 0 2
0 0 3 0 4
0 5 0 0 3
poprawną odpowiedzią jest:
39
Wyjaśnienie do przykładu:
Liczby napisane na rysunku krojem prostym oznaczają współczynniki ciekawości atrakcji,
a liczby napisane krojem pochyłym - dochody BajTouru za wysłanie wycieczki
do poszczególnych atrakcji.
Atrakcje odwiedzane na najbardziej dochodowej dla biura trasie zwiedzania są zaznaczone kółkami.
Za wysłanie wycieczki do tych atrakcji biuro otrzyma, kolejno, , , , i bajtalarów.
Dodatkowo, sumaryczny koszt przejazdu autokaru to bajtalarów.
Autor zadania: Jakub Radoszewski.